// PARALOGY_TREE_H
//

#if !defined(PARALOGY_TREE_H)
#define  PARALOGY_TREE_H

#include <vector>
#include <string>
#include <ostream>
#include "boost/tuple/tuple.hpp"
#include <utility>
#include <deque>
#include <map>
#include "matrix.h"
namespace bcpp_tree
{
//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	t_node

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
extern std::string enode_type_names[];
enum eNODETYPE {eNONE, eTAX1, eTAX2, eTAX1_GENE, eTAX2_GENE, eTAX1_TAX2,
				eTAX1_GENE_ORTH, eTAX2_GENE_ORTH,
				eTAX1_ORTH, eTAX2_ORTH, eTAX1_TAX2_ORTH};
class t_tree;
class do_sort_by_name;
class t_node
{
	friend class t_tree;
	friend class do_sort_by_name;
	t_tree*							tree;
	std::vector<t_node*>			children;
	double							length;
	double							len_to_root;
	double							len_to_leaf;
	unsigned						level;
	eNODETYPE						node_type;
	t_node* 						parent;
	bool 							leaf;
	unsigned						index;
//	static t_node*		create_root();
//	t_node*				add_leaf(const std::string& id);
//	t_node*				add_leaf();
	void				set_parent(t_node& new_parent);
public:
	void				print(std::ostream& os) const;

	t_tree*				get_tree() const			{	return tree;					}
	eNODETYPE			get_node_type() const		{	return node_type;				}
	t_node*				get_child(unsigned i)		{	return children[i];				}
	const t_node*		get_child(unsigned i) const	{	return children[i];				}
	unsigned			get_children_count() const	{	return children.size();			}
	unsigned			get_index()	const			{	return index; 					}
	unsigned			get_level()	const			{	return level; 					}
	double				get_length() const			{	return length;					}
	double				get_len_to_leaf() const		{	return len_to_leaf;				}
	double				get_len_to_root() const		{	return len_to_root;				}
	unsigned			get_leaf_index() const;
	const std::string&	get_name() const;
	const std::string&	get_label() const;
	t_node*				get_parent()				{	return parent;					}
	const t_node*		get_parent() const			{	return parent;					}
	bool				is_leaf() const				{	return leaf;					}

	void				set_level()						{level = parent->level+1;		}
	void				set_node_type(eNODETYPE l)		{node_type = l;					}
	void				set_length(double l)			{length = l;					}
	void				set_len_to_root(double l)		{len_to_root = l;				}
	void				set_len_to_leaf(double l)		{len_to_leaf = l;				}
	void				set_name(const std::string& n);
	void				set_label(const std::string& l);
private:
						t_node(t_tree* tree_, unsigned index,
								bool is_leaf, const std::string& name);
};


//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	t_tree

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
class t_tree
{
	friend class 				t_node;
	t_node*		 				root;
	t_node* 					current_node;
	t_node* 					current_parent;
	bool 						finished;
	std::deque<t_node>			shared_mem;
	std::vector<std::string>	node_names;
	std::vector<std::string>	node_labels;
	std::vector<t_node*>		leaves;
	unsigned					max_level;
	std::map<unsigned, unsigned> leaf_indices;
	t_node& 			add_node(bool is_leaf, const std::string& str, unsigned leaf_index = 0);
public:
	const std::vector<std::string>&	get_node_names () const	{return node_names;}
	const std::vector<std::string>&	get_node_labels () const{return node_labels;}

	void				to_matrix(t_matrix& matrix);
	void				reset();
	unsigned			get_leaf_count() const	{	return leaf_indices.size();		}
	t_node*				get_root() const {	return root;	}
	t_node&				get_leaf(unsigned i) const{	assert(i < leaves.size()); return *leaves[i];	}

	t_tree();
	t_node&				add_leaf(const std::string& str, unsigned leaf_index);
	t_node&				add_internal_node();
	t_node&				join_nodes(t_node& node1, t_node& node2);
	void 				label_current_node(const std::string& str);
	void 				reparent_to_grandparent();
	void 				set_branch_len(const std::string& str);
	void 				set_branch_len(double len);
	bool 				finish();
	bool				is_finished() const {return finished;}
	template <typename T> void for_each(T& t);
	template <typename T> void for_each(T& t) const;
};
//________________________________________________________________________________________

//	for_each

//________________________________________________________________________________________
template <typename T> void t_tree::for_each(T& t)
{
	for (unsigned i = 0; i < root->children.size(); ++i)
		t(root->children[i]);
}

template <typename T> void t_tree::for_each(T& t) const
{
	for (unsigned i = 0; i < root->children.size(); ++i)
		t(root->children[i]);
}



//________________________________________________________________________________________

//	new_hampshire format

//________________________________________________________________________________________
boost::tuple<bool, std::string>
		load_tree_from_newhampshire_format_str(const std::string& tree_str, t_tree& tree);



//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	t_node inlines

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
inline unsigned t_node::get_leaf_index() const
{
	return tree->leaf_indices[index];
}
inline const std::string& t_node::get_name() const
{
	return tree->node_names[index];
}
inline const std::string& t_node::get_label() const
{
	return tree->node_labels[index];
}
inline void t_node::set_name(const std::string& n)
{
	tree->node_names[index] =n;
}
inline void t_node::set_label(const std::string& l)
{
	tree->node_labels[index] = l;
}



//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	Operations

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
//________________________________________________________________________________________

//	do_newhampshire_format_str

//________________________________________________________________________________________
struct do_newhampshire_format_str
{
	std::ostream& os;
	do_newhampshire_format_str(std::ostream& os_) :os(os_){}
	void operator()(t_node* root);
	void recurse(t_node* node);
};

//________________________________________________________________________________________

//	do_set_levels

//________________________________________________________________________________________
struct do_set_levels
{
	unsigned max_level;
	void operator()(t_node* root) {max_level = 0; recurse(root);}
	void recurse(t_node* node);
};

//________________________________________________________________________________________

//	do_sort_by_name

//________________________________________________________________________________________
struct do_sort_by_name
{
	void operator()(t_node* root) {recurse(root);}
	const std::string* recurse(t_node* node);
};

//________________________________________________________________________________________

//	do_set_len_to_root

//________________________________________________________________________________________
struct do_set_len_to_root
{
	double max_len_to_leaf;
	void operator()(t_node* root);
	void recurse_len_to_root(t_node* node);
	void recurse_len_to_leaves(t_node* node);

};

//________________________________________________________________________________________

//	do_set_node_types

//________________________________________________________________________________________
struct do_set_node_types
{
	std::string tax1_matching_str;
	std::string tax2_matching_str;
	do_set_node_types(const std::string& s1, const std::string& s2) :
						tax1_matching_str(s1), tax2_matching_str(s2){}
	void operator()(t_node* root)	{	recurse(root);	}
	void recurse(t_node* node);
	void tag_ortholog_decendents(t_node* node);
};


//________________________________________________________________________________________

//	do_print_tree_full

//________________________________________________________________________________________
struct do_print_tree_full
{
	std::ostream& os;
	do_print_tree_full(std::ostream& os_):os(os_){}
	void operator()(t_node* root);
	void recurse(t_node* node);
};

//________________________________________________________________________________________

//	do_dump_nodes

//________________________________________________________________________________________
struct do_dump_nodes
{
	std::ostream& os;
	do_dump_nodes(std::ostream& os_) : os(os_){}
	void recurse(t_node* root);
	void operator()(t_node* node)	{	recurse(node);	}
};





//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	do_collect_orthologs

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct t_ortholog_data
{
	t_ortholog_data(): cnt_tax1(0), cnt_tax2(0){}
	std::vector<std::vector<std::string> >	ensg_sets;
	std::vector<std::vector<double> >		ensg_length_sets;
	unsigned				cnt_tax1;
	unsigned				cnt_tax2;
};
struct do_collect_orthologs
{
	t_ortholog_data ortho_1_to_1;
	t_ortholog_data ortho_1_to_m;
	t_ortholog_data ortho_m_to_1;
	t_ortholog_data ortho_m_to_m;
	t_ortholog_data orphaned_1_to_1;
	t_ortholog_data orphaned_1_to_m;
	t_ortholog_data orphaned_m_to_1;
	t_ortholog_data orphaned_m_to_m;
	t_ortholog_data orphaned_tax1;
	t_ortholog_data orphaned_tax2;
	std::vector<t_node*> tax1_genes;
	std::vector<t_node*> tax2_genes;
	void store_genes(t_ortholog_data* store);
	void store_orthologs(t_node* node);
	void store_orphaned_paralogs();
	void operator()(t_node* node)	{	recurse(node);	}
	void recurse(t_node* node);
};

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	do_sum_sqrs

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct do_sum_sqrs
{
	do_sum_sqrs(const t_matrix & matrix_)
		:matrix(matrix_), sum_sqrs(0.0), cnt_non_null_data(0){}
	const t_matrix&						matrix;
	std::deque<std::deque<unsigned> >	branches;
	double								sum_sqrs;
	double								avg_percent_stddev;
	unsigned							cnt_non_null_data;
	void operator()(t_node* root);
	void recurse(t_node* node, std::deque<unsigned>& parent_branch);
	void results(double& s, double& avg){s = sum_sqrs; avg = avg_percent_stddev;}
};


//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	do_sum_sqrs

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct do_sum_sqrs2
{
	do_sum_sqrs2(const t_matrix & matrix_)
		:matrix(matrix_), sum_sqrs(0.0), cnt_non_null_data(0){}
	const t_matrix&						matrix;
	std::deque<std::deque<unsigned> >	branches;
	double								sum_sqrs;
	double								avg_percent_stddev;
	unsigned							cnt_non_null_data;
	std::vector<double >				branch_lengths;
	std::vector<double >				branch_differences;
	void operator()(t_node* root);
	void recurse(t_node* node, std::deque<unsigned>& parent_branch);
	void results(double& s, double& avg){s = sum_sqrs; avg = avg_percent_stddev;}
};


//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	do_get_matrix

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct do_get_matrix
{
	do_get_matrix(t_matrix & matrix_)
		:matrix(matrix_){}
	t_matrix&				matrix;
	std::vector<double >	branch_lengths;
	void operator()(t_node* root);
	void recurse(t_node* node, std::deque<unsigned>& parent_branch);
};


class op_print_tree
{
	std::ostream&	os;
	const t_tree&	tree;
	unsigned		precision;
	unsigned		curr_level;
	mutable std::vector<char>	levels;
public:
	op_print_tree(const t_tree& tree_, unsigned p, std::ostream& os_):
			 os(os_), tree(tree_), precision(p), curr_level(0){}
	void operator()(const t_node* root) const {print (*root);};
	void print_horizontal_lines() const
	{
		os << std::string(precision + 2, '-');
	}
	void print_vertical_lines() const
	{
		for (unsigned i = 0; i < levels.size(); ++i)
			os << std::string(precision + 1, ' ') << (levels[i] ? '|' : ' ');
	}
	void print() const;
	void print(const t_node& curr_node) const;
	void recurse(const t_node& curr_node) const;
};


}
#endif

